package thired.class11_digui;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
//子序列
public class Class02_PrintAllSubsquences {
    public static List<String> subs(String s){
        char[] str = s.toCharArray();
        ArrayList<String> res = new ArrayList<>();
        String path = "";
        process(str,0,path,res);
        return res;
    }

    public static void process(char[] str,int index,String path,List<String> ans){
        if(index == str.length){
            ans.add(path);
            return;
        }
        process(str,index + 1,path,ans);
        process(str,index + 1,path + str[index],ans);
    }

    public static List<String> subsNoRepeat(String s){
        char[] str = s.toCharArray();
        HashSet<String> res = new HashSet<>();
        String path = "";
        process1(str,0,path,res);
        ArrayList<String> end = new ArrayList<>();
        end.addAll(res);
        return end;
    }

    public static void process1(char[] str,int index,String path,HashSet<String> ans){
        if(index == str.length){
            ans.add(path);
            return;
        }
        process1(str,index + 1,path,ans);
        process1(str,index + 1,path + str[index],ans);
    }


    public static void main(String[] args) {
        String test = "acccc";
        List<String> ans1 = subs(test);
        List<String> ans2 = subsNoRepeat(test);

        for (String str : ans1) {
            System.out.println(str);
        }
        System.out.println("=================");
        for (String str : ans2) {
            System.out.println(str);
        }
        System.out.println("=================");

    }
}
